﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Graph
{
    // edge list.
    public class BasicGraph : IBasicGraph
    {
        private IList<Vertex> vertices;
        private IList<Edge> edges;

        public int[,] adjMatrix;
        public int NoVer { get; set; }

        public BasicGraph(int noVer)
        {
            vertices = new List<Vertex>();
            adjMatrix = new int[noVer,noVer];
            this.NoVer = noVer;
            edges = new List<Edge>();
        }

        public int[,] getAdjMatrix()
        {
            return adjMatrix;
        }

        public IList<Vertex> VertexList
        {
            get{ return vertices;} 
        }

        public void AddVertex(Vertex vertex)
        {
                vertices.Add(vertex);
        }

        public void AddEdge(Vertex from, Vertex to)
        {
            //Console.WriteLine(from.Name + " = " +vertices.IndexOf(from) +  " " + to.Name + " = " + vertices.IndexOf(to));
            
            adjMatrix[vertices.IndexOf(from), vertices.IndexOf(to)] = 1;
            edges.Add(new Edge(from, to)); 
        }

        public void RemoveVertex(Vertex v)
        {
            vertices.Remove(v);
        }

        public void RemoveEdge(Vertex to, Vertex from)
        {
            adjMatrix[vertices.IndexOf(to), vertices.IndexOf(from)] = 0;
        }

        public bool ContainsVertex(Vertex vertex)
        {
            bool found = false;
            Vertex v = null;
            IEnumerator<Vertex> i = Vertices();
            while(i.MoveNext() && !found)
            {
                v = (Vertex) i.Current;
                if (v.Name.Equals(vertex.Name))
                {
                    found = true;
                }
            }
            return found;
        }

        public bool IsAdjacent(Vertex from, Vertex to)
        {
           return (adjMatrix[vertices.IndexOf(from), vertices.IndexOf(to)] == 1);
        }

        public IList GetAdjacencies(Vertex vertex)
        {
            int i = vertices.IndexOf(vertex);
            IList result = new List<Vertex>();

            for (int j = 0; j < GetNoOfVertices(); j++)
            {
                if (adjMatrix[i, j] == 1)
                    result.Add(vertices[j]);
            }
            return result;
        }

        public IEnumerator<Vertex> Vertices()
        {
            return vertices.GetEnumerator();
        }

        public IEnumerator Edges()
        {
            return edges.GetEnumerator();
        }

        public bool IsEmpty()
        {
            return (vertices.Count() == 0);
        }

        public int GetNoOfVertices()
        {
            return vertices.Count();
        }

        public int GetNoOfEdges()
        {
            int result = 0;
            int n = this.GetNoOfVertices();
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (adjMatrix[i, j] == 1) result++;
                }
            }
            return result;
        }

        public void Clear()
        {
            vertices = new List<Vertex>();
            adjMatrix = new int[NoVer, NoVer];
            edges = new List<Edge>();
        }

        //
        public Vertex GetNotMarkedVertex(Vertex v)
        {
            int i = vertices.IndexOf(v);
            int j = 0;
            while(j < GetNoOfVertices())
            {
                if(adjMatrix[i,j] ==1 && (vertices[j].Mark ==false))
                {
                    return vertices[j];
                }
                j++;
            }
            return null;
        }

        public void Unmark()
        {
            foreach (Vertex v in vertices)
            {
                v.Mark = false;
            }
        }

        public void PrintVertex(Vertex v)
        {
            Console.WriteLine(v.Name);
        }

        ///<summary>
        ///Returns a list of Vertices in dfs-order
        ///PRE The graph is connected and v is contained in the graph
        ///</summary>
        public IList DepthFirstSearch(Vertex ve)
        {
            Stack s = new Stack();
            IList result = new List<Vertex>();
            Vertex root = ve;
            root.Mark = true;
            PrintVertex(root);
            result.Add(root);
            s.Push(root);
            while(s.Count !=0)
            {
                Vertex v = (Vertex)s.Peek();
                Vertex child = GetNotMarkedVertex(v);
                if(child !=null)
                {
                    child.Mark = true;
                    PrintVertex(child);
                    result.Add(child);
                    s.Push(child);
                }
                else
                {
                    s.Pop();
                }
            }
            Unmark();
            return result;
        }

        public IList BredthFirstSearch(Vertex ve)
        {
            Queue q = new Queue();
            IList result = new List<Vertex>();
            Vertex root = ve;
            root.Mark = true;
            PrintVertex(root);
            result.Add(root);
            q.Enqueue(root);
            while(q.Count !=0)
            {
                Vertex v = (Vertex)q.Dequeue();
                Vertex child = null;
                while ((child=GetNotMarkedVertex(v))!=null)
                {
                    child.Mark = true;
                    PrintVertex(child);
                    result.Add(child);
                    q.Enqueue(child);
                }
            }
            Unmark();
            return result;
        }

        public Vertex findVertex(string name)
        {
            int i = 0;
            bool found = false;
            Vertex result = null;

            while (!found && i < GetNoOfVertices())
            {
                if (VertexList[i].Name.Equals(name))
                {
                    found = true;
                    result = VertexList[i];
                }
                else
                {
                    i++;
                }
            }
            return result;
        }
    }
}
